package Sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: homechen
 * Date: 2024-03-10
 * Time: 20:16
 */
public class insertSort {
    public static void InsertSort(int[] array) {
        int n = array.length;
        // 假设 [0,end-1] 是有序的，插入 end 位置，end 只能到 n-1的位置
        for (int i = 0; i < n - 1; i++) {
            int end = i;
            int tmp = array[end + 1];// 保存一下 end + 1 位置的值
            while (end >= 0) {
                if (array[end] > tmp) { // 后一个数，比前一个数小
                    array[end + 1] = array[end];
                    end--; // end 向前移动
                } else {
                    break;
                }
            }
            // 有两种情况，end = -1 | end > 0 都一样
            array[end + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 2, 5, 6, 2, 35, 3, 3, 55, 1, 3, 14, 53};
        InsertSort(array);
        System.out.println(Arrays.toString(array));
    }
}
